//#include <unistd.h>
//struct ListNode* reverseList(struct ListNode* head) {
//    struct ListNode* newhead = NULL, * cur = head;
//    while (cur) {
//        struct ListNode* next = cur->next;
//        cur->next = newhead;
//        newhead = cur;
//        cur = next;
//    }
//    return newhead;
//}
//struct ListNode* middleNode(struct ListNode* head) {
//    struct ListNode* slow = head, * fast = head;
//    while (fast && fast->next) {
//        fast = fast->next->next;
//        slow = slow->next;
//    }
//    return slow;
//}
//
//class PalindromeList {
//public:
//    bool chkPalindrome(ListNode* A) {
//        ListNode* cur1 = A;
//        ListNode* mid = middleNode(A);
//        ListNode* cur2 = reverseList(mid);
//        while (cur1 && cur2) {
//            if (cur1->val != cur2->val)
//                return false;
//            cur1 = cur1->next;
//            cur2 = cur2->next;
//        }
//        return true;
//    }
//};

//#include <cstdlib>
//class Partition {
//public:
//    ListNode* partition(ListNode* pHead, int x) {
//        ListNode* lguard, * ltail;
//        lguard = ltail = (ListNode*)malloc(sizeof(ListNode));
//        ListNode* gguard, * gtail;
//        gguard = gtail = (ListNode*)malloc(sizeof(ListNode));
//        gtail->next = ltail->next = NULL;
//        ListNode* cur = pHead;
//        while (cur) {
//            if (cur->val < x) {
//                ltail->next = cur;
//                ltail = ltail->next;
//            }
//            else {
//                gtail->next = cur;
//                gtail = gtail->next;
//            }
//            cur = cur->next;
//        }
//        ltail->next = gguard->next;
//        gtail->next = NULL;
//        ListNode* newhead = lguard->next;
//        free(gguard);
//        free(lguard);
//        return newhead;
//    }
//};

//struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {
//    int lena = 1, lenb = 1;
//    struct ListNode* cur1 = headA;
//    struct ListNode* cur2 = headB;
//    while (cur1->next) {
//        cur1 = cur1->next;
//        lena++;
//    }
//    while (cur2->next) {
//        cur2 = cur2->next;
//        lenb++;
//    }
//    if (cur1 != cur2)
//        return NULL;
//    struct ListNode* L = headA, * S = headB;
//    if (lena < lenb) {
//        L = headB, S = headA;
//    }
//    int k = fabs(lena - lenb);
//    while (k--) {
//        L = L->next;
//    }
//    while (L != S) {
//        L = L->next;
//        S = S->next;
//    }
//    return L;
//
//}

//bool hasCycle(struct ListNode* head) {
//    struct ListNode* slow = head, * fast = head;
//    while (fast && fast->next) {
//        slow = slow->next;
//        fast = fast->next->next;
//        if (fast == slow)
//            return true;
//    }
//    return false;
//}